//数组中的逆序对
class Solution {
public:
    int res=0;
    vector<int>tmp;
    int reversePairs(vector<int>& nums) 
    {
        int n=nums.size();
        tmp.resize(n);
        mergeSort(nums,0,nums.size()-1);
        return res;
    }
    void mergeSort(vector<int>&nums,int l,int r)
    {
        if(l>=r) return;
        int mid=(l+r)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);

        int i=0;
        int cur1=l,cur2=mid+1;
        while(cur1<=mid && cur2<=r)
        {
            if(nums[cur1]> nums[cur2]) res+=(r-cur2+1);
            tmp[i++]=nums[cur1]>nums[cur2]?nums[cur1++]:nums[cur2++];
        }
        while(cur1<=mid) tmp[i++]=nums[cur1++];
        while(cur2<=r) tmp[i++]=nums[cur2++];
        for(int i=l,j=0;i<=r;i++,j++)
        nums[i]=tmp[j];
    }
};
//计算右侧小于当前元素的个数
class Solution {
public:
    vector<int>res;//结果
    vector<int>tmp;//中间数组
    vector<int>index;//记录nums中当前元素的原始下标
    vector<int>tmpForIndex;//下标数组跟着数字数组一块动
    //unordered_map<int,int>hash; 有可能有重复元素
    vector<int> countSmaller(vector<int>& nums) 
    {
        int n=nums.size();
        res.resize(n);
        tmp.resize(n);
        tmpForIndex.resize(n);
        for(int i=0;i<n;i++) index.push_back(i);
        mergeSort(nums,0,n-1);
        return res;
    }
    void mergeSort(vector<int>&nums,int l,int r)
    {
        if(l>=r) return;
        int mid=(l+r)/2;
        mergeSort(nums,l,mid);
        mergeSort(nums,mid+1,r);

        int i=0;
        int cur1=l,cur2=mid+1;
        while(cur1<=mid && cur2<=r)
        {
            if(nums[cur1]>nums[cur2])
            {
                tmp[i]=nums[cur1];
                tmpForIndex[i]=index[cur1];
                res[tmpForIndex[i]]+=(r-cur2+1);
                i++,cur1++;
            }
            else 
            {
                tmp[i]=nums[cur2];
                tmpForIndex[i]=index[cur2];
                i++,cur2++;
            }    
        }
        while(cur1<=mid) 
        {
            tmpForIndex[i]=index[cur1];
            tmp[i++]=nums[cur1++];
        }
        while(cur2<=r) 
        {
            tmpForIndex[i]=index[cur2];
            tmp[i++]=nums[cur2++];
        }
        for(int i=l,j=0;i<=r;i++,j++)
        {
            nums[i]=tmp[j];
            index[i]=tmpForIndex[j];
        }
    }
};